package getLeastNumbers;

import java.util.Iterator;
import java.util.PriorityQueue;

/**@desc:
 * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
 *
 * 思路，这个题目是求中位数的基础，比求中位数要简单。
 * 我可以 A 他的大小是 K + 1 大小，我们先想 A 里面装 K 个数，然后把下一个数字，放到 A 里面，
 * 这时候，我们想把 A 里面的最大值弄出来，这样，在出现的这 5 个数里面最小的四个都在里面了。
 * 再来第 6 个数，思路是一样的，重复上面的过程就可以了。
 * @author wangyifei
 */
public class Solution {
    private PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>((x,y)->  y - x);
    private int numCounter = 1 ;
    public int[] getLastestNumber(int[] nums , int k){
        if(null == nums || nums.length < k){
            return null ;
        }
        int rsIdx = k - 1;
        int[] rs = new int[k];
        for(int num: nums){
            if(numCounter++ < k+1){
                bigRootHeap.offer(num);
            }else {
                bigRootHeap.offer(num);
                bigRootHeap.poll();
            }
        }
        while(!bigRootHeap.isEmpty()){
            rs[rsIdx--] = bigRootHeap.poll();
        }

        return rs ;
    }
    public static void main(String[] args) {
        int[] array = {4,5,1,6,2,7,3,8,10,6};
        Solution s = new Solution();
        for(int n :s.getLastestNumber(array,7)){
            System.out.println(n);
        }
    }
}
